from Algrithm.Trees.Base import create_tree

res = []
memo = []
def traverse(root):
    if not root:
        return "#"

    left = traverse(root.left)
    right = traverse(root.right)

    subTree = left +"," + right +","+str(root.val)

    if subTree in memo:
        res.append(root)
    else:
        memo.append(subTree)

    return subTree

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        minRes = []

        def midTraverse(root):
            if not root:
                return None
            midTraverse(root.left)
            minRes.append(root)
            midTraverse(root.right)

        midTraverse(pRootOfTree)
        # 主要是利用v和minRes两种表示法来改变双向链表的指针
        for k, v in enumerate(minRes[0:len(minRes) - 1]):
            v.right = minRes[k + 1]
            minRes[k + 1].left = v
        return minRes[0]
if __name__=="__main__":
    nums = [1,2,3,4,5,6,7,8,9]
    root = create_tree(nums)
    s = Solution()
    r =s.Convert(root)

